home *** CD-ROM | disk | FTP | other *** search
/ Experimental BBS Explossion 3 / Experimental BBS Explossion III.iso / c / tde31.zip / REGX.C < prev    next >
C/C++ Source or Header  |  1993-08-29  |  37KB  |  1,291 lines
  1. /*
  2.  * These functions compile a regular expression into an NFA and recognize
  3.  * a pattern.
  4.  *
  5.  * Regular expressions are often used to describe a pattern that might
  6.  * match several different or similar words.  An example of a regular
  7.  * expression subset is the wild card characters '*' and '?' used to list
  8.  * files in a directory.
  9.  *
  10.  * Might as well read the books and papers written by those who first wrote
  11.  * the various [a-z]?greps.  Ken Thompson was the author of grep.  In one
  12.  * weekend, Al Aho wrote egrep and fgrep.  Incidentally, when Dr. Aho was
  13.  * the guest speaker at the Distinguished Lecture Series at Georgia Tech,
  14.  * he personally autographed my copy of his book  _Compilers:  Principles,
  15.  * Techniques, and Tools_, aka the "Dragon Book."
  16.  *
  17.  * See:
  18.  *
  19.  *   Ken Thompson, "Regular Expression Search Algorithm."  _Communications
  20.  *      of the ACM_, 11 (No. 6): 419-422, 1968.
  21.  *
  22.  *   Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman, _Compilers: Principles,
  23.  *      Techniques, and Tools_, Addison-Wesley, Reading, Mass., 1986,
  24.  *      Chapter 3, "Lexical Analysis", pp 83-158.  ISBN 0-201-10088-6.
  25.  *
  26.  *   Robert Sedgewick, _Algorithms in C_, Addison-Wesley, Reading, Mass.,
  27.  *      1990, Chapter 20, "Pattern Matching", pp. 293-303, and Chapter 21,
  28.  *      "Parsing", pp. 305-317.  ISBN 0-201-51425-7.
  29.  *
  30.  *   Andrew Hume, "A Tale of Two Greps."  _Software--Practice and Experience_,
  31.  *      18 (No. 11): 1063-1072, 1988.
  32.  *
  33.  *
  34.  *                         Regular Expressions in TDE
  35.  *
  36.  * The core of the regular expression search algorithm in TDE is based on
  37.  * the nondeterministic finite-state machine in Dr. Segdewick's book.
  38.  * Additional parsing, operator precedence, and nfa construction and
  39.  * simulation info is from Dr. Aho's book.  The nfa node naming convention
  40.  * and additional nfa construction guidelines are from Ken Thompson's paper.
  41.  * I'm much too stupid to compile a regular expression into assembly language
  42.  * as suggested in Ken Thompson's paper, but I did get the idea to do the
  43.  * next best thing and added C library functions as NNODE terminal types.
  44.  *
  45.  * The local global NFA is builded with two arrays and a deque.  The
  46.  * first array, next1, in the NFA is used to hold the path for lambda
  47.  * transitions.  The second array, next2, is used to hold alternate paths.
  48.  * Next1 can hold all types of nodes, but it gets priority for lambda
  49.  * transitions.  The deque is a circular array where future states are queued
  50.  * in the head and present states are pushed in the tail.
  51.  *
  52.  * Searching for regular expressions in TDE is not very fast.  The worst
  53.  * case search, .*x, where x is any word or letter, is probably the slowest
  54.  * of any implementation with a regular expression search function.  However,
  55.  * TDE can handle a large regular expression subset.
  56.  *
  57.  * In version 3.1, I added BOW and EOW (beginning of word and end of word.)
  58.  *
  59.  * New editor name:  TDE, the Thomson-Davis Editor.
  60.  * Author:           Frank Davis
  61.  * Date:             June 5, 1991, version 1.0
  62.  * Date:             July 29, 1991, version 1.1
  63.  * Date:             October 5, 1991, version 1.2
  64.  * Date:             January 20, 1992, version 1.3
  65.  * Date:             February 17, 1992, version 1.4
  66.  * Date:             April 1, 1992, version 1.5
  67.  * Date:             June 5, 1992, version 2.0
  68.  * Date:             October 31, 1992, version 2.1
  69.  * Date:             April 1, 1993, version 2.2
  70.  * Date:             June 5, 1993, version 3.0
  71.  * Date:             August 29, 1993, version 3.1
  72.  *
  73.  * This code is released into the public domain, Frank Davis.
  74.  * You may use and distribute it freely.
  75.  */
  76.  
  77. #include "tdestr.h"
  78. #include "common.h"
  79. #include "tdefunc.h"
  80. #include "define.h"
  81.  
  82.  
  83. /*
  84.  * types of nodes in the NFA.
  85.  *
  86.  * let's use the node naming convention in Ken Thompson's reg ex paper.
  87.  */
  88. #define CNODE           0
  89. #define NNODE           1
  90.  
  91. #define SCAN            -1
  92.  
  93. /*
  94.  * types of terminals in NNODEs.
  95.  *
  96.  * starting with simple ASCII terminals, it's easy to build in other types of
  97.  *  terminals, e.g. wild chars, BOL, EOL, and character classes.  actually,
  98.  *  we can easily build ANSI C ctype library function NNODEs.
  99.  */
  100. #define STRAIGHT_ASCII  0
  101. #define IGNORE_ASCII    1
  102. #define WILD            2
  103. #define BOL             3
  104. #define EOL             4
  105. #define CLASS           5
  106. #define NOTCLASS        6
  107. #define WHITESPACE      7
  108. #define ALPHA           8
  109. #define UPPER           9
  110. #define LOWER           10
  111. #define ALPHANUM        11
  112. #define DECIMAL         12
  113. #define HEX             13
  114. #define BOW             14
  115. #define EOW             15
  116.  
  117.  
  118. /*
  119.  * types of terminals in CNODEs.
  120.  */
  121. #define START           0
  122. #define ACCEPT          1
  123. #define OR_NODE         2
  124. #define JUXTA           3
  125. #define CLOSURE         4
  126. #define ZERO_OR_ONE     5
  127.  
  128.  
  129. int  lookahead;
  130. int  regx_rc;
  131. int  reg_len;
  132. int  parser_state;
  133. char class_bits[32];
  134. int  bit[8] = { 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80 };
  135. int  c1;
  136. int  c2;
  137. int  ttype;
  138. int  regx_error_line;
  139.  
  140. NFA_TYPE  *nfa_pointer;
  141.  
  142. int  nfa_status;
  143. int  search_len;
  144. int  search_col;
  145. text_ptr search_string;
  146.  
  147. int  queued_states[REGX_SIZE+2];
  148. int  deque[REGX_SIZE*2];
  149. int  dq_head;
  150. int  dq_tail;
  151. int  stacked_node_count;
  152. int  reset_count;
  153.  
  154.  
  155. /*
  156.  * Name:    find_regx
  157.  * Purpose: To set up and find a regular expression.
  158.  * Date:    June 5, 1993
  159.  * Passed:  window:  pointer to current window
  160.  * Notes:   Keep the regular expression until changed.
  161.  */
  162. int  find_regx( WINDOW *window )
  163. {
  164. int  direction;
  165. int  new_string;
  166. char pattern[MAX_COLS];  /* text to be found */
  167. long found_line;
  168. long bin_offset;
  169. line_list_ptr ll;
  170. register WINDOW *win;  /* put window pointer in a register */
  171. int  rc;
  172. int  old_rcol;
  173. int  rcol;
  174.  
  175.    switch (g_status.command) {
  176.       case FindRegX :
  177.          new_string = TRUE;
  178.          direction  = FORWARD;
  179.          break;
  180.       case RepeatFindRegX :
  181.          new_string =  regx.search_defined != OK ? TRUE : FALSE;
  182.          direction  = FORWARD;
  183.          break;
  184.       case RepeatFindRegXBackward :
  185.          new_string =  regx.search_defined != OK ? TRUE : FALSE;
  186.          direction  = BACKWARD;
  187.          break;
  188.       default :
  189.          new_string = 0;
  190.          direction  = 0;
  191.          assert( FALSE );
  192.          break;
  193.    }
  194.  
  195.    win = window;
  196.    entab_linebuff( );
  197.    if (un_copy_line( win->ll, win, TRUE ) == ERROR)
  198.       return( ERROR );
  199.  
  200.    regx_error_line = win->bottom_line;
  201.  
  202.    /*
  203.     * get search text, using previous as default
  204.     */
  205.    rc = OK;
  206.    if (new_string == TRUE) {
  207.       *pattern = '\0';
  208.       if (regx.search_defined == OK) {
  209.  
  210.          assert( strlen( (char *)regx.pattern ) < MAX_COLS );
  211.  
  212.          strcpy( pattern, (char *)regx.pattern );
  213.       }
  214.  
  215.       /*
  216.        * string to find:
  217.        */
  218.       if (get_name( reg1, win->bottom_line, pattern,
  219.                     g_display.message_color ) != OK  ||  *pattern == '\0')
  220.          return( ERROR );
  221.       regx.search_defined = OK;
  222.  
  223.       assert( strlen( pattern ) < MAX_COLS );
  224.  
  225.       strcpy( (char *)regx.pattern, pattern );
  226.       rc = build_nfa( );
  227.       if (rc == ERROR)
  228.          regx.search_defined = ERROR;
  229.    }
  230.  
  231.    if (regx.search_defined == OK) {
  232.       old_rcol = win->rcol;
  233.       if (mode.inflate_tabs)
  234.          win->rcol = entab_adjust_rcol( win->ll->line, win->ll->len, win->rcol);
  235.       update_line( win );
  236.       show_search_message( SEARCHING, g_display.diag_color );
  237.       bin_offset = win->bin_offset;
  238.       if (direction == FORWARD) {
  239.          if ((ll = forward_regx_search( win, &found_line, &rcol )) != NULL) {
  240.             if (g_status.wrapped && g_status.macro_executing)
  241.                rc = ask_wrap_replace( win, &new_string );
  242.             if (rc == OK)
  243.                find_adjust( win, ll, found_line, rcol );
  244.             else
  245.                win->bin_offset = bin_offset;
  246.          }
  247.       } else {
  248.          if ((ll = backward_regx_search( win, &found_line, &rcol )) != NULL) {
  249.             if (g_status.wrapped && g_status.macro_executing)
  250.                rc = ask_wrap_replace( win, &new_string );
  251.             if (rc == OK)
  252.                find_adjust( win, ll, found_line, rcol );
  253.             else
  254.                win->bin_offset = bin_offset;
  255.          }
  256.       }
  257.       if (g_status.wrapped)
  258.          show_search_message( WRAPPED, g_display.diag_color );
  259.       else {
  260.          if (nfa_status == OK)
  261.             show_search_message( CLR_SEARCH, g_display.mode_color );
  262.          else
  263.             g_status.wrapped = TRUE;
  264.       }
  265.       if (ll == NULL) {
  266.          /*
  267.           * string not found
  268.           */
  269.          if (mode.inflate_tabs)
  270.             win->rcol = old_rcol;
  271.          combine_strings( pattern, find5a, (char *)regx.pattern, find5b );
  272.          error( WARNING, win->bottom_line, pattern );
  273.          rc = ERROR;
  274.       }
  275.       show_curl_line( win );
  276.       make_ruler( win );
  277.       show_ruler( win );
  278.    } else {
  279.       /*
  280.        * find pattern not defined
  281.        */
  282.       error( WARNING, win->bottom_line, find6 );
  283.       rc = ERROR;
  284.    }
  285.    return( rc );
  286. }
  287.  
  288.  
  289. /*
  290.  * Name:    forward_regx_search
  291.  * Purpose: search forward for regular expression
  292.  * Date:    June 5, 1993
  293.  * Passed:  window:  pointer to current window
  294.  *          rline:   pointer to real line counter
  295.  *          rcol:    pointer to real column variable
  296.  * Returns: position in file if found or NULL if not found
  297.  * Notes:   Start searching from cursor position to end of file.  If we hit
  298.  *           end of file without a match, start searching from the beginning
  299.  *           of file to cursor position.  (do wrapped searches)
  300.  */
  301. line_list_ptr forward_regx_search( WINDOW *window, long *rline, int *rcol )
  302. {
  303. register int len;
  304. int  i;
  305. int  end;
  306. register WINDOW *win;  /* put window pointer in a register */
  307. line_list_ptr ll;
  308.  
  309.    /*
  310.     * if cursor is beyond end of line then start at end of line
  311.     */
  312.    win  = window;
  313.    *rline = win->rline;
  314.    i = win->rcol + 1;
  315.    ll = win->ll;
  316.    len = ll->len;
  317.    if (i > len  &&  len != EOF) {
  318.       ll = ll->next;
  319.       ++*rline;
  320.       i = 0;
  321.    }
  322.    if (i < 0)
  323.       i = 0;
  324.  
  325.    *rcol = i;
  326.    ll = regx_search_forward( ll, rline, rcol );
  327.  
  328.    if (ll == NULL) {
  329.  
  330.       end = 0;
  331.       if (win->ll->next != NULL) {
  332.          end = win->ll->next->len;
  333.          win->ll->next->len = EOF;
  334.       }
  335.  
  336.       /*
  337.        * haven't found pattern yet - now search from beginning of file
  338.        */
  339.       g_status.wrapped = TRUE;
  340.  
  341.       *rcol = 0;
  342.       *rline = 1L;
  343.       ll = regx_search_forward( win->file_info->line_list, rline, rcol );
  344.  
  345.       if (ll == win->ll  &&  *rcol >= win->rcol)
  346.          ll = NULL;
  347.  
  348.       if (win->ll->next != NULL)
  349.          win->ll->next->len = end;
  350.    }
  351.    flush_keyboard( );
  352.  
  353.    if (ll != NULL)
  354.       bin_offset_adjust( win, *rline );
  355.    return( ll );
  356. }
  357.  
  358.  
  359. /*
  360.  * Name:    regx_search_forward
  361.  * Purpose: search forward for pattern using nfa
  362.  * Date:    June 5, 1993
  363.  * Passed:  ll:     pointer to current node in linked list
  364.  *          rline:  pointer to real line counter
  365.  *          col:    column in ll->line to begin search
  366.  * Returns: position in file if found or NULL if not found
  367.  * Notes:   run the nfa machine on each character in each line
  368.  */
  369. line_list_ptr regx_search_forward( line_list_ptr ll, long *rline, int  *col )
  370. {
  371.    if (ll->len == EOF)
  372.       return( NULL );
  373.    else {
  374.       switch (g_status.command) {
  375.          case DefineRegXGrep  :
  376.          case RepeatGrep :
  377.             nfa_pointer = &sas_nfa;
  378.             stacked_node_count = sas_regx.node_count;
  379.             break;
  380.          case FindRegX  :
  381.          case RepeatFindRegX :
  382.             nfa_pointer = &nfa;
  383.             stacked_node_count = regx.node_count;
  384.             break;
  385.          default :
  386.             assert( FALSE );
  387.             break;
  388.       }
  389.       nfa_status = OK;
  390.       search_string = ll->line;
  391.       search_len = ll->len;
  392.       search_col = *col;
  393.       reset_count = stacked_node_count * sizeof(int);
  394.       for (; !g_status.control_break;) {
  395.          for (; search_col <= search_len; search_col++) {
  396.             if (nfa_match( ) != ERROR) {
  397.                *col = search_col;
  398.                return( ll );
  399.             }
  400.          }
  401.          ++*rline;
  402.          ll = ll->next;
  403.          search_string = ll->line;
  404.          if (ll->len == EOF)
  405.             return( NULL );
  406.          search_len = ll->len;
  407.          search_col = 0;
  408.       }
  409.       return( NULL );
  410.    }
  411. }
  412.  
  413.  
  414. /*
  415.  * Name:    backward_regx_search
  416.  * Purpose: search backward for regular expression
  417.  * Date:    June 5, 1993
  418.  * Passed:  window:  pointer to current window
  419.  *          rline:   pointer to real line counter
  420.  *          rcol:    pointer to real column variable
  421.  * Returns: position in file if found or NULL if not found
  422.  * Notes:   Start searching from cursor position to end of file.  If we hit
  423.  *           end of file without a match, start searching from the beginning
  424.  *           of file to cursor position.  (do wrapped searches)
  425.  */
  426. line_list_ptr backward_regx_search( WINDOW *window, long *rline, int *rcol )
  427. {
  428. int  i;
  429. int  len;
  430. int  end;
  431. register WINDOW *win;  /* put window pointer in a register */
  432. line_list_ptr ll;
  433.  
  434.    win  = window;
  435.    *rline = win->rline;
  436.  
  437.    /*
  438.     * see if cursor is on EOF line.  if so, move search start to previous node.
  439.     */
  440.    if (win->ll->len != EOF) {
  441.       ll = win->ll;
  442.       i  = win->rcol - 1;
  443.       len = ll->len;
  444.       if (i >= len)
  445.          i = len - 1;
  446.    } else {
  447.       ll = win->ll->prev;
  448.       --*rline;
  449.       i = 0;
  450.       if (ll != NULL)
  451.          i = ll->len - 1;
  452.    }
  453.    *rcol = i;
  454.    ll = regx_search_backward( ll, rline, rcol );
  455.  
  456.    if (ll == NULL  &&  win->rline <= win->file_info->length) {
  457.  
  458.       end = 0;
  459.       if (win->ll->prev != NULL) {
  460.          end = win->ll->prev->len;
  461.          win->ll->prev->len = EOF;
  462.       }
  463.  
  464.       /*
  465.        * haven't found pattern yet - now search from end of file
  466.        */
  467.       g_status.wrapped = TRUE;
  468.       ll = win->file_info->line_list_end;
  469.       if (ll->prev != NULL)
  470.          *rcol = ll->prev->len;
  471.       else
  472.         *rcol = 0;
  473.       *rline = win->file_info->length;
  474.       ll = regx_search_backward( ll->prev, rline, rcol );
  475.  
  476.       if (ll == win->ll  &&  *rcol <= win->rcol)
  477.          ll = NULL;
  478.  
  479.       if (win->ll->prev != NULL)
  480.          win->ll->prev->len = end;
  481.    }
  482.    flush_keyboard( );
  483.  
  484.    if (ll != NULL)
  485.       bin_offset_adjust( win, *rline );
  486.    return( ll );
  487. }
  488.  
  489.  
  490. /*
  491.  * Name:    regx_search_backward
  492.  * Purpose: search backward for pattern using regular expression
  493.  * Date:    June 5, 1993
  494.  * Passed:  ll:     pointer to current node in linked list
  495.  *          rline:  pointer to real line counter
  496.  *          col:    column in ll->line to begin search
  497.  * Returns: position in file if found or NULL if not found
  498.  * Notes:   run the nfa machine on each character in each line
  499.  */
  500. line_list_ptr regx_search_backward( line_list_ptr ll, long *rline, int *col )
  501. {
  502.    if (ll == NULL)
  503.       return( NULL );
  504.    if (ll->len == EOF)
  505.       return( NULL );
  506.    else {
  507.       nfa_pointer = &nfa;
  508.       stacked_node_count = regx.node_count;
  509.  
  510.       search_string = ll->line;
  511.       search_len = ll->len;
  512.       search_col = *col;
  513.       reset_count = stacked_node_count * sizeof(int);
  514.       while (!g_status.control_break) {
  515.          for (; search_col >= 0; search_col--) {
  516.             if (nfa_match( ) != ERROR) {
  517.                *col = search_col;
  518.                return( ll );
  519.             }
  520.          }
  521.          --*rline;
  522.          ll = ll->prev;
  523.          if (ll == NULL)
  524.             return( NULL );
  525.          if (ll->len == EOF)
  526.             return( NULL );
  527.          search_string = ll->line;
  528.          search_col = search_len = ll->len;
  529.       }
  530.       return( NULL );
  531.    }
  532. }
  533.  
  534.  
  535. /******************************  NFA Recognizer  *********************/
  536.  
  537.  
  538. /*
  539.  * Name:    nfa_match
  540.  * Purpose: try to recognize a pattern
  541.  * Date:    June 5, 1993
  542.  * Passed:  none, but modifies local global nfa recognizer.
  543.  * Returns: length of recognized pattern if found or ERROR if not found.
  544.  */
  545. int  nfa_match( void )
  546. {
  547. register int c;
  548. int  state;
  549. int  j;
  550. int  n1;
  551. int  rc;
  552.  
  553.    j = search_col;
  554.    c  =  j < search_len  ?  search_string[j]  :  EOF;
  555.    state = nfa_pointer->next1[0];
  556.    dq_head = 0;
  557.    dq_tail = 0;
  558.    memset( queued_states, 0, reset_count );
  559.    put_dq( SCAN );
  560.  
  561.    while (state) {
  562.       if (state == SCAN) {
  563.          memset( queued_states, 0, reset_count );
  564.          j++;
  565.          put_dq( SCAN );
  566.          c  =  j < search_len  ?  search_string[j]  :  EOF;
  567.       } else if (nfa_pointer->node_type[state] == NNODE) {
  568.          n1 = nfa_pointer->next1[state];
  569.          rc = OK;
  570.          switch (nfa_pointer->term_type[state]) {
  571.             case STRAIGHT_ASCII :
  572.                if (nfa_pointer->c[state] == c)
  573.                   rc = put_dq( n1 );
  574.                break;
  575.             case IGNORE_ASCII   :
  576.                if (nfa_pointer->c[state] == tolower( c ))
  577.                   rc = put_dq( n1 );
  578.                break;
  579.             case WILD           :
  580.                if (j < search_len)
  581.                   rc = put_dq( n1 );
  582.                break;
  583.             case BOL            :
  584.                if (j == 0) {
  585.                   rc = put_dq( n1 );
  586.                   if (deque[dq_tail] == SCAN)
  587.                      --j;
  588.                }
  589.                break;
  590.             case EOL            :
  591.                if (j == search_len) {
  592.                   rc = put_dq( n1 );
  593.                   if (deque[dq_tail] == SCAN)
  594.                      --j;
  595.                }
  596.                break;
  597.             case CLASS          :
  598.                if (c != EOF  &&  nfa_pointer->class[state][c/8] & bit[c%8])
  599.                   rc = put_dq( n1 );
  600.                break;
  601.             case NOTCLASS       :
  602.                if (c != EOF  &&  !(nfa_pointer->class[state][c/8] & bit[c%8]))
  603.                   rc = put_dq( n1 );
  604.                break;
  605.             case WHITESPACE     :
  606.                if (c == ' '  ||  c == '\t')
  607.                   rc = put_dq( n1 );
  608.                break;
  609.             case ALPHA          :
  610.                if (c != EOF  &&  isalpha( c ))
  611.                   rc = put_dq( n1 );
  612.                break;
  613.             case UPPER          :
  614.                if (c != EOF  &&  isupper( c ))
  615.                   rc = put_dq( n1 );
  616.                break;
  617.             case LOWER          :
  618.                if (c != EOF  &&  islower( c ))
  619.                   rc = put_dq( n1 );
  620.                break;
  621.             case ALPHANUM       :
  622.                if (c != EOF  &&  isalnum( c ))
  623.                   rc = put_dq( n1 );
  624.                break;
  625.             case DECIMAL        :
  626.                if (c != EOF  &&  isdigit( c ))
  627.                   rc = put_dq( n1 );
  628.                break;
  629.             case HEX            :
  630.                if (c != EOF  &&  isxdigit( c ))
  631.                   rc = put_dq( n1 );
  632.                break;
  633.             case BOW            :
  634.                if (c != EOF) {
  635.                   if (!myiswhitespc( c )) {
  636.                      if (j == 0) {
  637.                         rc = put_dq( n1 );
  638.                         if (deque[dq_tail] == SCAN)
  639.                            --j;
  640.                      } else if (j > 0) {
  641.                         if (myiswhitespc( search_string[j-1] )) {
  642.                            rc = put_dq( n1 );
  643.                            if (deque[dq_tail] == SCAN)
  644.                               --j;
  645.                         }
  646.                      }
  647.                   }
  648.                }
  649.                break;
  650.             case EOW            :
  651.                if (c == EOF) {
  652.                   if (search_len > 0) {
  653.                      if (!myiswhitespc( search_string[search_len-1] )) {
  654.                         rc = put_dq( n1 );
  655.                         if (deque[dq_tail] == SCAN)
  656.                            --j;
  657.                      }
  658.                   }
  659.                } else {
  660.                   if (myiswhitespc( c )  &&  j > 0) {
  661.                      if (!myiswhitespc( search_string[j-1] )) {
  662.                         rc = put_dq( n1 );
  663.                         if (deque[dq_tail] == SCAN)
  664.                            --j;
  665.                      }
  666.                   }
  667.                }
  668.                break;
  669.             default             :
  670.                assert( FALSE );
  671.                break;
  672.          }
  673.          if (rc == ERROR)
  674.             return( 0 );
  675.       } else {
  676.          assert( nfa_pointer->node_type[state] == CNODE );
  677.  
  678.          n1 = nfa_pointer->next1[state];
  679.          if (push_dq( n1 ) == ERROR)
  680.             return( 0 );
  681.  
  682.          if (n1 != nfa_pointer->next2[state])
  683.             if (push_dq( nfa_pointer->next2[state] ) == ERROR)
  684.                return( 0 );
  685.       }
  686.       if (dequeempty( )  ||  j > search_len)
  687.          return( ERROR );
  688.       state = pop_dq( );
  689.    }
  690.    return( j - search_col );
  691. }
  692.  
  693.  
  694. /*
  695.  * Name:    put_dq
  696.  * Purpose: queue future states
  697.  * Date:    June 5, 1993
  698.  * Passed:  v:  state to queue
  699.  * Returns: none, but modifies local global deque variables.  future
  700.  *           states are queued in the head.
  701.  * Notes:   do not add any duplicate states to the head of the deque.
  702.  */
  703. int  put_dq( int v )
  704. {
  705.    if (queued_states[v+1] == 0) {
  706.       ++queued_states[v+1];
  707.       deque[dq_head] = v;
  708.       dq_head--;
  709.       if (dq_head < 0)
  710.          dq_head = REGX_SIZE - 1;
  711.       if (dq_tail == dq_head) {
  712.          nfa_status = ERROR;
  713.          show_search_message( NFA_GAVE_UP, g_display.diag_color );
  714.          return( ERROR );
  715.       }
  716.    }
  717.    return( OK );
  718. }
  719.  
  720.  
  721. /*
  722.  * Name:    push_dq
  723.  * Purpose: push state on deque
  724.  * Date:    June 5, 1993
  725.  * Passed:  v:  state to push
  726.  * Returns: whether stack is OK or if stack overflowed - ERROR.  present
  727.  *           states are stacked.
  728.  */
  729. int  push_dq( int v )
  730. {
  731.    ++dq_tail;
  732.    if (dq_tail == dq_head) {
  733.       nfa_status = ERROR;
  734.       show_search_message( NFA_GAVE_UP, g_display.diag_color );
  735.       return( ERROR );
  736.    } else {
  737.       if (dq_tail > REGX_SIZE - 1)
  738.          dq_tail = 0;
  739.       deque[dq_tail] = v;
  740.       return( OK );
  741.    }
  742. }
  743.  
  744.  
  745. /*
  746.  * Name:    pop_dq
  747.  * Purpose: pop next state on dq
  748.  * Date:    June 5, 1993
  749.  * Passed:  none, but looks at local global nfa recognizer
  750.  * Returns: state on top of deque and decrements stack pointer
  751.  */
  752. int  pop_dq( void )
  753. {
  754. register int v;
  755.  
  756.    v = deque[dq_tail];
  757.    dq_tail--;
  758.    if (dq_tail < 0)
  759.       dq_tail = REGX_SIZE - 1;
  760.    return( v );
  761. }
  762.  
  763.  
  764. /*
  765.  * Name:    dequeempty
  766.  * Purpose: any room on dq?
  767.  * Date:    June 5, 1993
  768.  * Passed:  none, but looks at local global nfa recognizer
  769.  * Returns: boolean, TRUE if empty.
  770.  * Notes:   the deque is a circular array where future states are
  771.  *           queued in the head and present states are pushed in the tail.
  772.  */
  773. int  dequeempty( void )
  774. {
  775.    if (dq_tail > dq_head)
  776.       return( dq_tail - dq_head == 1 );
  777.    else
  778.       return( dq_tail + REGX_SIZE - dq_head == 1 );
  779. }
  780.  
  781.  
  782. /***************************  NFA Compiler  **************************/
  783.  
  784.  
  785. /*
  786.  * Name:    build_nfa
  787.  * Purpose: initialize nfa and call the compiler
  788.  * Date:    June 5, 1993
  789.  * Passed:  none, but looks at local global pattern.
  790.  * Returns: whether or not an ERROR occured
  791.  * Notes:   sets up the initial variables for the compiler.  builds
  792.  *          initial and acceptor states for the nfa after compiler finishes.
  793.  */
  794. int  build_nfa( void )
  795. {
  796.    regx_rc = OK;
  797.  
  798.    init_nfa( );
  799.    lookahead = 0;
  800.    reg_len   = strlen( (char *)regx.pattern );
  801.    parser_state = 1;
  802.  
  803.    nfa.next1[0] = expression( );
  804.    if (regx_rc == OK) {
  805.       emit_cnode( 0, START, nfa.next1[0], nfa.next1[0] );
  806.       emit_cnode( parser_state, ACCEPT, 0, 0 );
  807.       regx.node_count = parser_state + 2;
  808.    }
  809.  
  810.    if (g_status.command == DefineRegXGrep) {
  811.       memcpy( &sas_nfa, &nfa, sizeof(NFA_TYPE) );
  812.       memcpy( &sas_regx, ®x, sizeof(REGX_INFO) );
  813.    }
  814.    return( regx_rc );
  815. }
  816.  
  817.  
  818. /*
  819.  * Name:    expression
  820.  * Purpose: break reg ex into terms and expressions
  821.  * Date:    June 5, 1993
  822.  * Passed:  none, but looks at local global pattern.
  823.  * Returns: none
  824.  * Notes:   because recursion can go fairly deep, almost all variables
  825.  *          were made local global.  no need to save most of this stuff
  826.  *          on the stack.
  827.  */
  828. int  expression( void )
  829. {
  830. int t1;
  831. int t2;
  832. int r;
  833.  
  834.    t1 = term( );
  835.    r = t1;
  836.    if (regx.pattern[lookahead] == '|') {
  837.       lookahead++;
  838.       parser_state++;
  839.       r = t2 = parser_state;
  840.       parser_state++;
  841.       emit_cnode( t2, OR_NODE, expression( ), t1 );
  842.       emit_cnode( t2-1, JUXTA, parser_state, parser_state );
  843.  
  844.       /*
  845.        * the OR_NODE seems to need a path from the previous node
  846.        */
  847.       if (nfa.node_type[t1] == CNODE)
  848.          t1 = min( nfa.next1[t1], nfa.next2[t1] );
  849.       nfa.next1[t1-1] = t2;
  850.       if (nfa.node_type[t1-1] == NNODE)
  851.          nfa.next2[t1-1] = t2;
  852.    }
  853.    return( r );
  854. }
  855.  
  856.  
  857. /*
  858.  * Name:    term
  859.  * Purpose: break reg ex into factors and terms
  860.  * Date:    June 5, 1993
  861.  * Passed:  none, but looks at local global pattern.
  862.  * Returns: none
  863.  */
  864. int  term( void )
  865. {
  866. int r;
  867.  
  868.    r = factor( );
  869.    if (regx.pattern[lookahead] == '('  ||  letter( regx.pattern[lookahead] ))
  870.       term( );
  871.    else if (Kleene_star( regx.pattern[lookahead] ))
  872.       regx_error( reg11 );
  873.    return( r );
  874. }
  875.  
  876.  
  877. /*
  878.  * Name:    factor
  879.  * Purpose: add NNODEs and CNODEs to local global nfa
  880.  * Date:    June 5, 1993
  881.  * Passed:  none
  882.  * Returns: none, but modifies local global nfa.
  883.  * Notes:   this function does most of the compiling.  it recognizes all
  884.  *          NNODEs, predefined macros, escape characters, and operators.
  885.  */
  886. int  factor( void )
  887. {
  888. int t1;
  889. int t2;
  890. int r;
  891. int c;
  892. int paren;
  893.  
  894.    t1 = parser_state;
  895.    c = regx.pattern[lookahead];
  896.    if (c == '(') {
  897.       lookahead++;
  898.       t2 = expression( );
  899.       if (regx.pattern[lookahead] == ')') {
  900.          lookahead++;
  901.          paren = TRUE;
  902.       } else
  903.  
  904.          /*
  905.           * unmatched open parens
  906.           */
  907.          regx_error( reg2 );
  908.    } else if (letter( c )) {
  909.       paren = FALSE;
  910.       switch (c) {
  911.          case ']' :
  912.  
  913.             /*
  914.              * unmatched close bracket
  915.              */
  916.             regx_error( reg9 );
  917.             break;
  918.          case '.' :
  919.             ttype = WILD;
  920.             break;
  921.          case ',' :
  922.             ttype = WHITESPACE;
  923.             break;
  924.          case '^' :
  925.             ttype = BOL;
  926.             break;
  927.          case '$' :
  928.             ttype = EOL;
  929.             break;
  930.          case '<' :
  931.             ttype = BOW;
  932.             break;
  933.          case '>' :
  934.             ttype = EOW;
  935.             break;
  936.          case '\\' :
  937.             ++lookahead;
  938.             ttype =  mode.search_case == IGNORE ? IGNORE_ASCII : STRAIGHT_ASCII;
  939.             if (lookahead != '\0') {
  940.                if (regx.pattern[lookahead] != ':')
  941.                   c = escape_char( regx.pattern[lookahead] );
  942.  
  943.                /*
  944.                 * predefined unix-like macros.
  945.                 */
  946.                else {
  947.                   c = regx.pattern[lookahead+1];
  948.                   if (c != '\0') {
  949.                      switch (c) {
  950.                         case 'a' :
  951.                            ++lookahead;
  952.                            ttype = ALPHANUM;
  953.                            break;
  954.                         case 'b' :
  955.                            ++lookahead;
  956.                            ttype = WHITESPACE;
  957.                            break;
  958.                         case 'c' :
  959.                            ++lookahead;
  960.                            ttype = ALPHA;
  961.                            break;
  962.                         case 'd' :
  963.                            ++lookahead;
  964.                            ttype = DECIMAL;
  965.                            break;
  966.                         case 'h' :
  967.                            ++lookahead;
  968.                            ttype = HEX;
  969.                            break;
  970.                         case 'l' :
  971.                            ++lookahead;
  972.                            ttype = LOWER;
  973.                            break;
  974.                         case 'u' :
  975.                            ++lookahead;
  976.                            ttype = UPPER;
  977.                            break;
  978.                         default :
  979.                            c = escape_char( regx.pattern[lookahead] );
  980.                            break;
  981.                      }
  982.                   } else
  983.                      c = escape_char( regx.pattern[lookahead] );
  984.                }
  985.             } else
  986.                regx_error( reg4 );
  987.             break;
  988.          case '[' :
  989.             memset( class_bits, 0, sizeof(char) * 32 );
  990.             ++lookahead;
  991.             if (lookahead != '\0') {
  992.                c = regx.pattern[lookahead];
  993.                if (c == '^') {
  994.                   ++lookahead;
  995.                   ttype = NOTCLASS;
  996.                } else
  997.                   ttype = CLASS;
  998.  
  999.                c1 = regx.pattern[lookahead];
  1000.                do {
  1001.                   class_bits[c1/8]  |=  bit[c1%8];
  1002.                   if (c1 != '\0')
  1003.                      ++lookahead;
  1004.                   if (regx.pattern[lookahead] == '-') {
  1005.                      ++lookahead;
  1006.                      c2 = regx.pattern[lookahead];
  1007.                      if (c2 != '\0') {
  1008.  
  1009.                         /*
  1010.                          * just in case the hi for the range is given first,
  1011.                          *  switch c1 and c2,  e.g. [9-0].
  1012.                          */
  1013.                         if (c2 < c1) {
  1014.                            c  = c2;
  1015.                            c2 = c1;
  1016.                            c1 = c;
  1017.                         }
  1018.  
  1019.                         for (c=c1; c <= c2; c++)
  1020.                            class_bits[c/8] |= bit[c%8];
  1021.  
  1022.                         if (regx.pattern[lookahead] != '\0')
  1023.                            ++lookahead;
  1024.                      } else
  1025.                         regx_error( reg10 );
  1026.                   }
  1027.                   c1 = regx.pattern[lookahead];
  1028.                } while (c1  != '\0'  &&  c1 != ']');
  1029.  
  1030.                if (c1 == '\0')
  1031.                   regx_error( reg5 );
  1032.             } else
  1033.                regx_error( reg6 );
  1034.             break;
  1035.          default :
  1036.             if (mode.search_case == IGNORE) {
  1037.                c = tolower( c );
  1038.                ttype = IGNORE_ASCII;
  1039.             } else
  1040.                ttype = STRAIGHT_ASCII;
  1041.       }
  1042.       emit_nnode( parser_state, ttype, c, parser_state+1, parser_state+1 );
  1043.       if (ttype == CLASS  ||  ttype == NOTCLASS) {
  1044.          nfa.class[parser_state] = calloc( 32, sizeof(char) );
  1045.          if (nfa.class[parser_state] != NULL)
  1046.             memcpy( nfa.class[parser_state], class_bits, sizeof( char )*32 );
  1047.          else
  1048.             regx_error( reg7 );
  1049.       }
  1050.       t2 = parser_state;
  1051.       lookahead++;
  1052.       parser_state++;
  1053.    } else if (c == '\0')
  1054.       return( 0 );
  1055.    else {
  1056.       if (c == '*'  ||  c == '+'  ||  c == '?')
  1057.          regx_error( reg8 );
  1058.       else if (c  ==  ')')
  1059.          regx_error( reg3 );
  1060.       else
  1061.          regx_error( reg2 );
  1062.    }
  1063.  
  1064.    c = regx.pattern[lookahead];
  1065.    switch (c) {
  1066.       case '*' :
  1067.          emit_cnode( parser_state, CLOSURE, parser_state+1, t2 );
  1068.          r = parser_state;
  1069.          if (nfa.node_type[t1] == CNODE)
  1070.             t1 = min( nfa.next1[t1], nfa.next2[t1] );
  1071.          nfa.next1[t1-1] = parser_state;
  1072.          if (nfa.node_type[t1-1] == NNODE)
  1073.             nfa.next2[t1-1] = parser_state;
  1074.          lookahead++;
  1075.          parser_state++;
  1076.          paren = FALSE;
  1077.          break;
  1078.       case '+' :
  1079.          if (paren == TRUE) {
  1080.             emit_cnode( parser_state, JUXTA, parser_state+2, parser_state+2 );
  1081.             parser_state++;
  1082.          }
  1083.  
  1084.          emit_cnode( parser_state, JUXTA, t2, t2 );
  1085.          r = parser_state;
  1086.          parser_state++;
  1087.  
  1088.          if (paren == FALSE) {
  1089.             nfa.next1[t2] = parser_state;
  1090.             if (nfa.node_type[t2] == NNODE)
  1091.                nfa.next2[t2] = parser_state;
  1092.          }
  1093.  
  1094.          emit_cnode( parser_state, CLOSURE, parser_state+1, t2 );
  1095.          if (nfa.node_type[t1] == CNODE)
  1096.             t1 = min( nfa.next1[t1], nfa.next2[t1] );
  1097.          nfa.next1[t1-1] = r;
  1098.          if (nfa.node_type[t1-1] == NNODE)
  1099.             nfa.next2[t1-1] = r;
  1100.          parser_state++;
  1101.          lookahead++;
  1102.          paren = FALSE;
  1103.          break;
  1104.       case '?' :
  1105.          emit_cnode( parser_state, JUXTA, parser_state+2, parser_state+2 );
  1106.          parser_state++;
  1107.          r = parser_state;
  1108.          emit_cnode( parser_state, ZERO_OR_ONE, parser_state+1, t2 );
  1109.          if (nfa.node_type[t1] == CNODE)
  1110.             t1 = min( nfa.next1[t1], nfa.next2[t1] );
  1111.          nfa.next1[t1-1] = parser_state;
  1112.          if (nfa.node_type[t1-1] == NNODE)
  1113.             nfa.next2[t1-1] = parser_state;
  1114.          parser_state++;
  1115.          lookahead++;
  1116.          paren = FALSE;
  1117.          break;
  1118.       default  :
  1119.          r = t2;
  1120.          break;
  1121.    }
  1122.  
  1123.    /*
  1124.     * close parens seem to need a JUXTA node to gather all reg ex's
  1125.     *  to a common point.
  1126.     */
  1127.    if (paren) {
  1128.       emit_cnode( parser_state, JUXTA, parser_state+1, parser_state+1 );
  1129.       parser_state++;
  1130.    }
  1131.    return( r );
  1132. }
  1133.  
  1134.  
  1135. /*
  1136.  * Name:    escape_char
  1137.  * Purpose: recognize escape and C escape sequences
  1138.  * Date:    June 5, 1993
  1139.  * Passed:  let:  letter to escape
  1140.  * Returns: escaped letter
  1141.  */
  1142. int  escape_char( int let )
  1143. {
  1144.    switch (let) {
  1145.       case '0' :
  1146.          let = 0x00;
  1147.          break;
  1148.       case 'a' :
  1149.          let = 0x07;
  1150.          break;
  1151.       case 'b' :
  1152.          let = 0x08;
  1153.          break;
  1154.       case 'n' :
  1155.          let = 0x0a;
  1156.          break;
  1157.       case 'r' :
  1158.          let = 0x0d;
  1159.          break;
  1160.       case 't' :
  1161.          let = 0x09;
  1162.          break;
  1163.       default  :
  1164.          break;
  1165.    }
  1166.    return( let );
  1167. }
  1168.  
  1169.  
  1170. /*
  1171.  * Name:    emit_cnode
  1172.  * Purpose: add a null node to our pattern matching machine
  1173.  * Date:    June 5, 1993
  1174.  * Passed:  index:  current node in nfa
  1175.  *          ttype:  terminal type - CLOSURE, OR, JUXTA, etc...
  1176.  *          n1:     pointer to next state, path for lambda transitions
  1177.  *          n2:     pointer to other next state, usually a NNODE
  1178.  * Returns: none, but modifies local global nfa.
  1179.  */
  1180. void emit_cnode( int index, int ttype, int n1, int n2 )
  1181. {
  1182.    assert( index >= 0);
  1183.    assert( index < REGX_SIZE );
  1184.  
  1185.    nfa.node_type[index] = CNODE;
  1186.    nfa.term_type[index] = ttype;
  1187.    nfa.c[index] = 0;
  1188.    nfa.next1[index] = n1;
  1189.    nfa.next2[index] = n2;
  1190. }
  1191.  
  1192.  
  1193. /*
  1194.  * Name:    emit_nnode
  1195.  * Purpose: add a to our pattern matching machine
  1196.  * Date:    June 5, 1993
  1197.  * Passed:  index:  current node in nfa
  1198.  *          ttype:  terminal type - EOL, ASCII, etc...
  1199.  *          c:      letter this node recognizes
  1200.  *          n1:     pointer to next state
  1201.  *          n2:     pointer to other next state, which can be same as n1
  1202.  * Returns: none, but modifies local global nfa.
  1203.  */
  1204. void emit_nnode( int index, int ttype, int c, int n1, int n2 )
  1205. {
  1206.    assert( index >= 0);
  1207.    assert( index < REGX_SIZE );
  1208.  
  1209.    nfa.node_type[index] = NNODE;
  1210.    nfa.term_type[index] = ttype;
  1211.    nfa.c[index] = c;
  1212.    nfa.next1[index] = n1;
  1213.    nfa.next2[index] = n2;
  1214. }
  1215.  
  1216.  
  1217. /*
  1218.  * Name:    init_nfa
  1219.  * Purpose: set local global nfa to NULL state
  1220.  * Date:    June 5, 1993
  1221.  * Passed:  none
  1222.  */
  1223. void init_nfa( void )
  1224. {
  1225. int i;
  1226.  
  1227.    for (i=0; i < REGX_SIZE; i++) {
  1228.       nfa.node_type[i] = NNODE;
  1229.       nfa.term_type[i] = 0;
  1230.       nfa.c[i] = 0;
  1231.       nfa.next1[i] = 0;
  1232.       nfa.next2[i] = 0;
  1233.       if (nfa.class[i] != NULL)
  1234.          free( nfa.class[i] );
  1235.       nfa.class[i] = NULL;
  1236.    }
  1237. }
  1238.  
  1239.  
  1240. /*
  1241.  * Name:    regx_error
  1242.  * Purpose: display reg ex error message and set reg ex error code
  1243.  * Date:    June 5, 1993
  1244.  * Passed:  line:  line to display error
  1245.  * Returns: none, but sets reg ex return code to error.
  1246.  */
  1247. void regx_error( char *line )
  1248. {
  1249.    error( WARNING, regx_error_line, line );
  1250.    regx_rc = ERROR;
  1251. }
  1252.  
  1253.  
  1254. /*
  1255.  * Name:    separator
  1256.  * Purpose: determine if character is a reg ex separator
  1257.  * Date:    June 5, 1993
  1258.  * Passed:  let:  letter to look at
  1259.  * Returns: whether or not 'let' is a separator
  1260.  */
  1261. int  separator( int let )
  1262. {
  1263.    return( let == 0  ||  let == ')'  ||  let == '|' );
  1264. }
  1265.  
  1266.  
  1267. /*
  1268.  * Name:    Kleene_star
  1269.  * Purpose: determine if character is a reg ex operator
  1270.  * Date:    June 5, 1993
  1271.  * Passed:  let:  letter to look at
  1272.  * Returns: whether or not 'let' is a letter
  1273.  */
  1274. int  Kleene_star( int let )
  1275. {
  1276.    return( let == '*'  ||  let == '+'  ||  let == '?' );
  1277. }
  1278.  
  1279.  
  1280. /*
  1281.  * Name:    letter
  1282.  * Purpose: determine if character is a recognized reg ex character
  1283.  * Date:    June 5, 1993
  1284.  * Passed:  let:  letter to look at
  1285.  * Returns: whether or not 'let' is a letter.
  1286.  */
  1287. int  letter( int let )
  1288. {
  1289.    return( !separator( let )  &&  !Kleene_star( let ) );
  1290. }
  1291.